#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <queue>
#include <iostream>
using namespace std;

#define InfoType int     // 定义权值数据类型
#define INFINITY INT_MAX // 宏常量定义无穷
#define VertexType char  // 顶点数据类型
#define MaxVertexNum 20  // 顶点数目最大值
typedef struct
{
    VertexType Vertex[MaxVertexNum];      // 顶点表
    int Edge[MaxVertexNum][MaxVertexNum]; // 领接矩阵，边表
    int vexNum, arcNum;                   // 顶点数，边数
    bool directed;                        // true:有向图,false:无向图
} MGraph;

void Adjacent(MGraph *G, int x, int y);                       // 判断图G是否存在边<x，y> 或(x，y)。
void Neighbors(MGraph *G, int x);                             // 列出图G中与结点x邻接的边。
void InsertVertex(MGraph *G, int x);                          // 在图G中插入顶点x。
void DeleteVertex(MGraph *G, int x);                          // 从图G中删除顶点x。
void AddEdge(MGraph *G, int x, int y, int weighted);          // 若无向边(x，y)或有向边 <x,y>不存在，则向图G中添加该边。
void RemoveEdge(MGraph *G, int x, int y);                     // 若无向边(x, y)或有向边<x，y> 存在，则从图G中删除该边。
int FirstNeighbor(MGraph *G, int x);                          // 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回 - 1。
int NextNeighbor(MGraph *G, int x, int y);                    // 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的项点号，若y是x的最后一个邻接点，则返回 - 1。
InfoType Get_edge_value(MGraph *G, int x, int y);             // 获取图G中边(x, y)或<x,y> 对应的权值。
InfoType Set_edge_value(MGraph *G, int x, int y, InfoType v); // 设置图G中边(x，y)或<x,y> 对应的权值为v。
void Show_MGraph(MGraph *G);                                  // 输出领接矩阵

void Visit(int v);            // 访问图结点
void InitMGraph(MGraph *G);   // 初始化领接表
void CreateMGraph(MGraph *G); // 创建领接表存储图
bool visited[MaxVertexNum];   // 访问标记数组
queue<int> Q;                 // C++STL创建队列Q

// BFS广度优先遍历算法
void BFSTraverse(MGraph *G); // 对图G进行广度优先遍历
void BFS(MGraph *G, int v);  // 从顶点V出发，广度优先遍历G

// DFS深度优先遍历算法算法
void DFSTraverse(MGraph *G); // 对图G进行深度优先遍历
void DFS(MGraph *G, int v);  // 从顶点V出发，广度优先遍历G

// 最短路径算法
int dist[MaxVertexNum]; // d[i]表示从u到i结点的最短路径长度
int path[MaxVertexNum]; // path[i]表示最短路径中的上一个顶点

// BFS最短路径算法
void BFS_MIN_DISTANCE(MGraph *G, int u); // 无向图中求顶点u到其他顶点的最短路径

// Dijkstra最短路径算法，单源，只能用于权值为正的图
bool final[MaxVertexNum];              // 标记各顶点是否已找到最短路径
void ShortestPath_Dijkstra(MGraph *G); // Dijkstra算法， 求有向网G的V0顶点到其余顶点v的最短路径及带权长度D[v]
// path[v]的值为前驱顶点下标, dist[v]表示V0到v的最短路径长度和

// Floyd最短路径算法，可以用于负权值图，但不能有负权值回路。用一次就可以求出任意一对顶点间的最短路径
int A[MaxVertexNum][MaxVertexNum];    // 目前看来，各顶点间的最短路径长度
int Path[MaxVertexNum][MaxVertexNum]; // 两个顶点之间的前一个中转顶点
void ShortestPath_Floyd(MGraph *G);   // Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]

int main()
{
    MGraph G;
    CreateMGraph(&G);
    // BFSTraverse(&G);
    // DFSTraverse(&G);
    cout << endl;
    // Show_MGraph(&G);

    cout << "Dijkstra:" << endl;
    ShortestPath_Dijkstra(&G);

    // cout << "Floyd:" << endl;
    // ShortestPath_Floyd(&G);
    return 0;
}
void InsertVertex(MGraph *G, int x) // 在图G中插入顶点x。
{
    assert(G != NULL);
    if (G->Vertex[x] == 0)
        G->vexNum++;
    G->Vertex[x] = x + 'A';
    return;
}
void DeleteVertex(MGraph *G, int x) // 从图G中删除顶点x。
{
    assert(G != NULL);
    if (G->Vertex[x] == 0)
        return;
    G->vexNum--;
    for (int i = 0; i < G->vexNum; i++)
    {
        if (G->Edge[x][i] > 0)
        {
            G->Edge[x][i] = 0;
            G->arcNum--;
        }
    }
    if (G->directed == true)
        return;
    for (int i = 0; i < G->vexNum; i++)
    {
        if (G->Edge[i][x] > 0)
        {
            G->Edge[i][x] = 0;
        }
    }
}
void AddEdge(MGraph *G, int x, int y, int weighted) // 若无向边(x，y)或有向边 <x,y>不存在，则向图G中添加该边。
{
    assert(G != NULL);
    if (G->Edge[x][y] > 0)
        return;
    G->arcNum++;
    int weight = 1;
    if (weighted)
    {
        printf("Enter the weight of the vertex:");
        scanf("%d", &weight);
    }
    G->Edge[x][y] = weight;
    if (G->directed == false)
        G->Edge[y][x] = weight;
}
void RemoveEdge(MGraph *G, int x, int y) // 若无向边(x, y)或有向边<x，y> 存在，则从图G中删除该边。
{
    assert(G != NULL);
    if (G->Edge[x][y] == 0)
        return;
    G->arcNum--;
    G->Edge[x][y] = 0;
    if (G->directed == false)
        G->Edge[y][x] = 0;
    return;
}
int FirstNeighbor(MGraph *G, int x) // 求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回 - 1。
{
    assert(G != NULL);
    int i = 0;
    for (i = 0; i < G->vexNum; i++)
    {
        if (i != x && G->Edge[x][i] > 0)
        {
            return i;
        }
    }
    return -1;
}
int NextNeighbor(MGraph *G, int x, int y) // 假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的项点号，若y是x的最后一个邻接点，则返回 - 1。
{
    assert(G != NULL);
    int i = 0;
    for (i = y + 1; i < G->vexNum; i++)
    {
        if (i != x && G->Edge[x][i] > 0)
        {
            return i;
        }
    }
    return -1;
}
void Show_MGraph(MGraph *G) // 输出领接矩阵
{
    int i = 0, j = 0;
    for (i = 0; i < G->vexNum; i++)
    {
        for (j = 0; j < G->vexNum; j++)
        {
            cout << G->Edge[i][j] << ' ';
        }
        cout << endl;
    }
}
void InitMGraph(MGraph *G) // 初始化领接表,边存在则值>0，不存在则等于0
{
    assert(G != NULL);
    int i = 0;
    for (i = 0; i < MaxVertexNum; i++)
    {
        G->Vertex[i] = 0;
        for (int j = 0; j < MaxVertexNum; j++)
        {
            G->Edge[i][j] = 0;
        }
    }
    G->vexNum = 0;
    G->arcNum = 0;
    return;
}
void CreateMGraph(MGraph *G) // 创建领接表存储图
{
    assert(G != NULL);
    InitMGraph(G);
    int i = 0;
    printf("Directed(1) or undirected(0)?\n");
    scanf("%d", &i);
    if (i == 1)
        G->directed = true;
    else
        G->directed = false;
    printf("Weighted(1) or no weighted(0)?\n");
    int weighted = 0;
    scanf("%d", &weighted);
    printf("How many vertices do you want to insert?(0~20)\n");
    scanf("%d", &i);
    int j = 0;
    for (j = 0; j < i; j++)
    {
        InsertVertex(G, j);
    }
    printf("Enter the arcs.Enter\"x y\"to add (x,y) or <x,y>.Enter -1 to come an end.\n");
    if (weighted)
        printf("Enter a number of the weight of (x,y) or <x,y> after you enter \"x y\" to attach it.\n");
    int x, y;
    scanf("%d", &x);
    while (x != -1)
    {
        scanf("%d", &y);
        AddEdge(G, x, y, weighted);
        scanf("%d", &x);
    }
}
void BFSTraverse(MGraph *G) // 对图G进行广度优先遍历
{
    for (int i = 0; i < G->vexNum; i++)
    {
        visited[i] = false; // 访问标记数组初始化
    }
    // InitQueue(Q); // 初始化辅助队列

    for (int i = 0; i < G->vexNum; i++)
    {
        if (!visited[i]) // 对每个连通分量调用一次BFS
            BFS(G, i);   // vi未访问过，从vi开始BFS
    }
}
void Visit(int v) // 访问图结点
{
    printf("%d ", v);
}
void BFS(MGraph *G, int v) // 从顶点V出发，广度优先遍历G
{
    Visit(v); // 访问初始顶点v
    printf("\n");
    visited[v] = true; // 对v做已访问标记
    Q.push(v);         // v入队Q
    while (!Q.empty())
    {
        v = Q.front(); // v等于队首元素
        Q.pop();       // 出队
        int flag = 0;
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) // 检测所有邻接点
        {
            if (!visited[w]) // w为v尚未访问的邻接点
            {
                Visit(w); // 访问结点w
                flag = 1;
                visited[w] = true; // 标记W
                Q.push(w);         // 出队
            }
        }
        if (flag)
            printf("\n");
    }
}
void DFSTraverse(MGraph *G) // 对图G进行深度优先遍历
{
    int i = 0;
    Q = queue<int>(); // 清空队列
    for (i = 0; i < G->vexNum; i++)
    {
        visited[i] = false;
    }
    for (i = 0; i < G->vexNum; i++)
    {
        if (!visited[i])
        {
            DFS(G, i);
            printf("\n");
        }
    }
    return;
}
void DFS(MGraph *G, int v) // 从顶点V出发，广度优先遍历G
{
    Visit(v);
    visited[v] = true;
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    {
        if (!visited[w])
            DFS(G, w);
    }
    return;
}
void BFS_MIN_DISTANCE(MGraph *G, int u) // 无向图中求顶点u到其他顶点的最短路径
{
    int i = 0;
    for (i = 0; i < G->vexNum; i++)
    {
        visited[i] = false; // 访问标记数组初始化
    }
    Q = queue<int>(); // 清空队列
    for (i = 0; i < G->vexNum; i++)
    {
        dist[i] = INT_MAX; // 初始化路径长度
        path[i] = -1;      // 最短路径从哪个顶点过来
    }
    dist[u] = 0;
    visited[u] = true;
    Q.push(u);
    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
        {
            if (!visited[w])
            {
                dist[w] = dist[u] + 1;
                path[w] = u;
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}
void ShortestPath_Dijkstra(MGraph *G) // Dijkstra算法， 求有向网G的V0顶点到其余顶点v的最短路径及带权长度D[v]
{
    int i = 0;
    int j = 0;
    int k = 0;
    for (i = 0; i < G->vexNum; i++) // 初始化存储数组
    {
        final[i] = false;
        // 初始化路径长度
        if (G->Edge[0][i] == 0)
            dist[i] = INFINITY;
        else
            dist[i] = G->Edge[0][i];
        path[i] = -1; // 最短路径从哪个顶点过来
    }
    final[0] = true;
    dist[0] = 0;
    int Min = INFINITY;             // 当前所求得离V0最近顶点
    for (i = 1; i < G->vexNum; i++) // 主循环，每次找V0到某个顶点V的最短路径
    {
        Min = INFINITY;
        for (j = 1; j < G->vexNum; j++) // 找离V0最近的顶点
        {
            if (!final[j] && dist[j] < Min) // 顶点j离V0更近且顶点j还没找到最短路径
            {
                k = j;
                Min = dist[j];
            }
        }
        final[k] = true; // 目前找到最近的顶点
        for (j = 0; j < G->vexNum; j++)
        {
            // 找到了更短路径
            if (!final[j] && (Min + G->Edge[k][j] < dist[j]) && G->Edge[k][j]) // 把G->Edge[k][j]!=0的条件也加进去判断，因为该值等于0时，以下操作无意义，但其他两个条件可能同时满足
            {
                dist[j] = Min + G->Edge[k][j]; // 更新更短路径值
                path[j] = k;                   // 更新更短路径前驱顶点
            }
        }
    }
    for (i = 1; i < G->vexNum; i++) // 输出最短路径
    {
        printf("V%d", i);
        j = path[i];
        while (j != -1)
        {
            printf("<-");
            printf("V%d", j);
            j = path[j];
        }
        printf("<-V0\n");
    }
}
void ShortestPath_Floyd(MGraph *G) // Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]
{
    // 初始化矩阵A和矩阵Path
    int i = 0, j = 0, k = 0;
    for (i = 0; i < G->vexNum; i++)
    {
        for (j = 0; j < G->vexNum; j++)
        {
            if (G->Edge[i][j] == 0 && i != j)
                A[i][j] = INFINITY;
            else
                A[i][j] = G->Edge[i][j];
            Path[i][j] = -1;
        }
    }
    for (k = 0; k < G->vexNum; k++)
    {
        for (i = 0; i < G->vexNum; i++)
        {
            for (j = 0; j < G->vexNum; j++)
            {
                if (A[i][k] + A[k][j] < A[i][j] && A[i][k] != INFINITY && A[k][j] != INFINITY) // 如果经过下标为k顶点路径比原两点间路径更短；加两个非无穷判断，防止爆int
                {
                    A[i][j] = A[i][k] + A[k][j]; // 将当前两点间权值设为更小的一个
                    Path[i][j] = k;              // 路径设置为经过下标为k的顶点
                }
            }
        }
    }
    // 输出最短路径
    printf("各顶点间最短路径如下:\n");
    for (i = 0; i < G->vexNum; i++)
    {
        for (j = 0; j < G->vexNum; j++)
        {
            if (A[i][j] == INFINITY)
                printf("%d no path to %d\n", i, j);
            else
            {
                printf("%d to %d weighted route length:%d   ", i, j, A[i][j]);
                printf("path:%d", i);
                k = Path[i][j];
                while (k != -1)
                {
                    printf("->%d", k);
                    k = Path[k][j];
                }
                printf("->%d\n", j);
            }
        }
        printf("\n");
    }

    // printf("最短路径D\n");
    // for (v = 0; v < G->vexNum; ++v)
    // {
    //     for (w = 0; w < G->vexNum; ++w)
    //     {
    //         printf("%d\t", D[v][w]);
    //     }
    //     printf("\n");
    // }
    // printf("最短路径P\n");
    // for (v = 0; v < G->vexNum; ++v)
    // {
    //     for (w = 0; w < G->vexNum; ++w)
    //     {
    //         printf("%d ", P[v][w]);
    //     }
    //     printf("\n");
    // }
}
